/*
 * @lc app=leetcode.cn id=402 lang=typescript
 *
 * [402] 移掉 K 位数字
 */

// @lc code=start
function removeKdigits(num: string, k: number): string {
  if (k >= num.length) return '0';
  // 单调递增栈
  const stack = [];
  for (const c of num) {
    // 找到高位比较大的数组，且k要大于0
    while (stack.length && k > 0 && c < stack[stack.length - 1]) {
      stack.pop();
      k--;
    }
    stack.push(c);
  }
  // 如果k大于0，表示num中有小于k个元素满足不满足单调递增性
  // 栈中剩下的元素都是递增的，所以只有从后面把最大的弹出就可以了。
  while (k-- > 0) {
    stack.pop();
  }

  let ans = '';
  for (const c of stack) {
    if (c === '0' && ans === '') continue;
    ans += c;
  }

  return ans === '' ? '0' : ans;
}
// @lc code=end
